

<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 11, Exercise 3<BR>

<BR>

</H1>







<HR class = coderule>

<pre class = code>

<strong class=var>AbstractDataType</strong> <em cass=var>DIndexedBSTree</em> {

   <strong class=var>instances</em>

      Same as for <code class=code>DBSTree</em> except that each node has a <code class=code>LeftSize</em> field.

   <strong class=var>operations</em>

      <em cass=var>Create():</em> create an empty indexed binary search tree

      <em cass=var>Search(k, e):</em> return in <em class=var>e</em> any element with key <em class=var>k</em>

                    return <code class=code>false</em> if the operation fails,

                    return <code class=code>true</em> if it succeeds

      <em cass=var>IndexSearch(k, e):</em> return in <em class=var>e</em> the <em class=var>k</em>th element

      <em cass=var>Insert(e):</em> insert element <em class=var>e</em> into the search tree

      <em cass=var>Delete(k, e):</em> delete any element with key <em class=var>k</em> and return it in <em class=var>e</em>

      <em cass=var>IndexDelete(k, e):</em> delete the <em class=var>k</em>th element and return it in <em class=var>e</em>

      <em cass=var>Ascend():</em> output all elements in nondecreasing order of key

}

<hr class=coderule>

</pre>



</FONT>

</BODY>

</HTML>

